home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 21 / CU Amiga Magazine's Super CD-ROM 21 (1998)(EMAP Images)(GB)[!][issue 1998-04].iso / CUCD / Utilities / PGP / source / pgp50i-b8a / tools / heap.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-01-04  |  3.4 KB  |  145 lines
  1. /*
  2.  * heap.c -- Simple priority queue.  Takes pointers to cost values
  3.  * (presumably the first field in a larger structure) and returns
  4.  * them in increasing order of cost.
  5.  *
  6.  * Copyright (C) 1997 Pretty Good Privacy, Inc.
  7.  *
  8.  * Written by Colin Plumb and Mark H. Weaver
  9.  *
  10.  * $Id: heap.c,v 1.2 1997/07/05 02:55:23 colin Exp $
  11.  */
  12.  
  13. #include <stdio.h>    /* For fprintf(stderr, "Out of memory") */
  14. #include <stdlib.h>    /* For malloc() & co. */
  15.  
  16. #include "heap.h"
  17.  
  18. #define HeapParent(i)            ((i) / 2)
  19. #define HeapLeftChild(i)        ((i) * 2)
  20. #define HeapRightChild(i)        ((i) * 2 + 1)
  21. #define HeapElem(h, i)            (h)->elems[i]
  22. #define HeapMinElem(h)            HeapElem(h, 1)
  23. #define HeapElemCost(e)            (*(e))
  24. #define HeapCost(h, i)            HeapElemCost(HeapElem(h, i))
  25. #define HeapSize(h)                ((h)->numElems)
  26.  
  27. static void
  28. SiftDown(Heap const *heap, HeapCost *e)
  29. {
  30.     HeapIndex size = HeapSize(heap), parent = 1, child;
  31.     HeapCost cparent = HeapElemCost(e), cchild;
  32.  
  33.     for (;;) {
  34.         child = 2*parent;
  35.         if (child > size)
  36.             break;
  37.         cchild = HeapCost(heap, child);
  38.         if (child < size && cchild > HeapCost(heap, child+1)) {
  39.             cchild = HeapCost(heap, child+1);
  40.             child++;
  41.         }
  42.         if (cparent <= cchild)
  43.             break;    /* Stop sifting down */
  44.         HeapElem(heap, parent) = HeapElem(heap, child);
  45.         parent = child;
  46.     }
  47.     HeapElem(heap, parent) = e;
  48. }
  49.  
  50. /* Debug tool: verify heap property */
  51. void
  52. HeapVerify(Heap *heap)
  53. {
  54.     HeapIndex i;
  55.  
  56.     for (i = 2; i <= HeapSize(heap); i++)
  57.         if (HeapCost(heap, i) < HeapCost(heap, HeapParent(i)))
  58.             fprintf(stderr, "DEBUG: VerifyHeap failed at elem %d\n", i);
  59. }
  60.  
  61. /* Remove and return the minimum cost from the heap. */
  62. HeapCost *
  63. HeapGetMin(Heap *heap)
  64. {
  65.     HeapIndex lastElem = HeapSize(heap);
  66.     HeapCost *retval;
  67.  
  68.     if (!lastElem)
  69.         return NULL;
  70.     retval = HeapMinElem(heap);
  71.     HeapSize(heap) = lastElem-1;
  72.     SiftDown(heap, HeapElem(heap, lastElem));
  73.     return retval;
  74. }
  75.  
  76. /* Helper - set heap size, reallocating if needed */
  77. static void
  78. HeapResize(Heap *heap, HeapIndex newNumElems)
  79. {
  80.     if (newNumElems >= heap->elemsAllocated) {
  81.         HeapIndex newAllocSize = heap->elemsAllocated * 2;
  82.  
  83.         if (newAllocSize <= newNumElems)
  84.             newAllocSize = newNumElems + 1;
  85.         heap->elems = (HeapCost **)realloc((void *)heap->elems,
  86.                                       sizeof(*heap->elems) * newAllocSize);
  87.         if (heap->elems == NULL) {
  88.             fprintf(stderr, "Fatal error: Out of memory growing heap\n");
  89.             exit(1);
  90.         }
  91.         heap->elemsAllocated = newAllocSize;
  92.     }
  93.     heap->numElems = newNumElems;
  94. }
  95.  
  96. /* Add an element to the heap */
  97. void
  98. HeapInsert(Heap *heap, HeapCost *newElem)
  99. {
  100.     HeapIndex parent, i = ++HeapSize(heap);
  101.     HeapCost cost = HeapElemCost(newElem);
  102.  
  103.     HeapResize(heap, i);
  104.     /* Sift up until parent = 0 */
  105.     while ((parent = HeapParent(i)) && HeapCost(heap, parent) > cost) {
  106.         HeapElem(heap, i) = HeapElem(heap, parent);
  107.         i = parent;
  108.     }
  109.     heap->elems[i] = newElem;
  110. }
  111.  
  112. /* Initialize a new heap */
  113. void
  114. HeapInit(Heap *heap, HeapIndex initSize)
  115. {
  116.     initSize++;    /* Add one for temporary element */
  117.     if (initSize < 1)
  118.         initSize = 1;
  119.     heap->elems = (HeapCost **)malloc(initSize * sizeof(*heap->elems));
  120.     if (heap->elems == NULL) {
  121.         fprintf(stderr, "Fatal error: Out of memory creating heap\n");
  122.         exit(1);
  123.     }
  124.     heap->elemsAllocated = initSize;
  125.     heap->numElems = 0;
  126. }
  127.  
  128. /* Free up a heap's resources. */
  129. void
  130. HeapDestroy(Heap *heap)
  131. {
  132.     free((void *)heap->elems);
  133.     heap->elemsAllocated = 0;
  134.     heap->numElems = 0;
  135.     heap->elems = NULL;
  136. }
  137.  
  138. /*
  139.  * Local Variables:
  140.  * tab-width: 4
  141.  * End:
  142.  * vi: ts=4 sw=4
  143.  * vim: si
  144.  */
  145.